package examples.Fpidigits where

{-
    A little bit faster than the Java version it was derived from
    with n=100000 it takes runtime 3468.549 wallclock seconds.
    Java needs runtime: 3817.946
    
    This is funny, as the frege program has been adapted from the java source
    (with the help of the then current Haskell source).
    Anyway, the core of the algorithm is the same.
    But perhaps frege code is just better food for the JIT.
    
    Here is the original java code:
    
    /* The Great Computer Language Shootout
   http://shootout.alioth.debian.org/

   contributed by Isaac Gouy
    */

import java.math.BigInteger;

public class Jpidigits {
   static final int L = 10;

   public static void main(String args[]) {
      long t0 = System.currentTimeMillis();
      int n = Integer.parseInt(args[0]);
      int j = 0;

      PiDigitSpigot digits = new PiDigitSpigot();

      while (n > 0){
         if (n >= L){
            for (int i=0; i<L; i++) System.out.print( digits.next() );
            j += L;
         } else {
            for (int i=0; i<n; i++) System.out.print( digits.next() );
            for (int i=n; i<L; i++) System.out.print(" ");
            j += n;
         }
         System.out.print("\t:"); System.out.println(j);
         n -= L;
      }
      long t1 = System.currentTimeMillis();
      System.err.println("runtime: " + (t1-t0)/1000.0);
   }
}


class PiDigitSpigot {
   Transformation z, x, inverse;

   public PiDigitSpigot(){
      z = new Transformation(1,0,0,1);
      x = new Transformation(0,0,0,0);
      inverse = new Transformation(0,0,0,0);
   }

   public int next(){
      int y = digit();
      if (isSafe(y)){
         z = produce(y); return y;
      } else {
         z = consume( x.next() ); return next();
      }
   }

   public int digit(){
      return z.extract(3);
   }

   public boolean isSafe(int digit){
      return digit == z.extract(4);
   }

   public Transformation produce(int i){
      return ( inverse.qrst(10,-10*i,0,1) ).compose(z);
   }

   public Transformation consume(Transformation a){
      return z.compose(a);
   }
}


class Transformation {
   BigInteger q, r, s, t;
   int k;

   public Transformation(int q, int r, int s, int t){
      this.q = BigInteger.valueOf(q);
      this.r = BigInteger.valueOf(r);
      this.s = BigInteger.valueOf(s);
      this.t = BigInteger.valueOf(t);
      k = 0;
   }

   public Transformation(BigInteger q, BigInteger r, BigInteger s, BigInteger t){
      this.q = q;
      this.r = r;
      this.s = s;
      this.t = t;
      k = 0;
   }

   public Transformation next(){
      k++;
      q = BigInteger.valueOf(k);
      r = BigInteger.valueOf(4 * k + 2);
      s = BigInteger.valueOf(0);
      t = BigInteger.valueOf(2 * k + 1);
      return this;
   }

   public int extract(int j){
      BigInteger bigj = BigInteger.valueOf(j);
      BigInteger numerator = (q.multiply(bigj)).add(r);
      BigInteger denominator = (s.multiply(bigj)).add(t);
      return ( numerator.divide(denominator) ).intValue();
   }

   public Transformation qrst(int q, int r, int s, int t){
      this.q = BigInteger.valueOf(q);
      this.r = BigInteger.valueOf(r);
      this.s = BigInteger.valueOf(s);
      this.t = BigInteger.valueOf(t);
      k = 0;
      return this;
   }

   public Transformation compose(Transformation a){
      return new Transformation(
         q.multiply(a.q)
         ,(q.multiply(a.r)).add( (r.multiply(a.t)) )
         ,(s.multiply(a.q)).add( (t.multiply(a.s)) )
         ,(s.multiply(a.r)).add( (t.multiply(a.t)) )
         );
   }
}   
-}
-- import frege.List ()
-- import frege.lib.ForkJoin


data F = F {!q :: Integer, !r :: Integer, !s :: Integer, !t :: Integer}

main [] = main ["1000"]
main (arg:_) 
    | Right n <- arg.int  = do -- loop 10 0 (str2 f0 1) n
            loop2 n 0 (next f0 1)
    | otherwise = println "Please specify the number of pi digits"
    where 
        loop2 !n i (d,z,k)
            | i < n = {- nxt `par` -} do
                print d
                when ((i+1) `rem` 10 == 0) do
                    print "\t:"
                    println (i+1)
                loop2 n (i+1) nxt
            | i == n && i `rem` 10 == 0 = return ()
            | otherwise = do
                print ' '
                if (i+1) `rem` 10 == 0 then do
                    print "\t:"
                    println n
                else loop2 n (i+1) (d,z,k)
            where nxt = next z k
        

f0 = F 1 0 0 1

fi :: Int -> F
fi n = let k = n.big in F k (4*k+2) 0 (2*k+1)

flr  x           (F q r s t) = (q*x + r) `quot` (s*x + t)
comp1 (F q r s t) (F u v w x) = F (q*u+r*w) (q*v+r*x) (t*w) (t*x)
comp2 (F q r s t) (F u v w x) = F (q*u) (q*v+r*x) (s*u) (s*v+t*x)


next z !n
    | y == flr 4 z = let
            !f = F 10 ((-10)*y) 0 1
            !cfz = comp1 f z
        in (y.int, cfz, n)
    | otherwise = next (comp2 z (fi n)) (n+1)
    where
        y = flr 3 z